package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _87二叉搜索树中第K小的元素
 * @description
 * @date 2023/08/05 9:23
 * <p>
 * ******************************************************
 */
public class _87二叉搜索树中第K小的元素 {
    int res = -1;
    int times;
    public int kthSmallest(TreeNode root, int k) {
        times = k;
        inOrder(root);
        return res;
    }

    private void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            inOrder(root.left);
        }
        if (times == 1) {
            res = root.val;
        }
        times--;
        if (root.right != null) {
            inOrder(root.right);
        }
    }

    public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
}
